Multiprocessor devices comprise two or more processors executing processes, i.e., processor executable instructions, in combination. Executing processes comprise all or a portion of operating systems, application programs, device drivers, etc. Processor executable instructions may be provided in the form of one or more threads for execution by the processor. In multiprocessor devices, threads may be allocated to a processor for execution in various manners. For example, particular thread types may be assigned to a particular processor. Additionally, a number of threads from an application program or that provide a particular function may be assigned to the same processor for execution. The threads may also be assigned to one of a number of processors.
A process is a container for a set of instructions that carry out all or a portion of the overall task of an application program. Processes comprise executing application programs, managed by operating system components such as a scheduler and a memory management program. A process context comprises the executable instructions, data (used by the executable instructions), and stack (memory used when the process is running). A process is a representation of an executing application program and a thread is a fraction of the program. A thread is a sequence of executing instructions of a program. A particular type of thread is a kernel thread. Kernel threads exist within the context of a process and provide the operating system the means to address and execute smaller segments of the process. Threads allow application programs to be broken up into logically distinct tasks. Each thread can be scheduled, synchronized, and prioritized with respect to one or more threads on one or more processors.
When a thread becomes ready for execution by a processor it is said to be a “runnable” thread. The scheduler places the runnable thread on a run queue. The target run queue selection for the runnable thread is performed based on thread scheduling parameters such as scheduling policy, scheduling priority, and processor or non uniform memory access (NUMA) affinity, as well as scheduler run queue structuring. The thread is then placed on the run queue after acquiring a lock for synchronization, i.e., a run queue lock. When a processor becomes available to execute a thread, the processor selects a thread from a run queue, removes the selected thread from the run queue, and executes the thread. The act of removing the thread from the run queue involves acquiring the run queue lock. This mechanism of using run queues to manage runnable threads may face several performance throughput issues on systems having idle processors.